package 数组算法;

/**
 * @Classname islandPerimeterV2
 * @Description TODO
 * @Date 2022/3/22 7:19
 * @Created by xjl
 */
public class islandPerimeter463V2 {
    // 表示的四个方向
    static int[] dx = {0, 1, 0, -1};
    static int[] dy = {1, 0, -1, 0};

    /**
     * @description 判断格子周围是否为水，所以是需要的遍历格子，判断他的四个方向是否为水或者是超过了范围的结果
     * @param: grid
     * @date: 2022/3/22 7:19
     * @return: int
     * @author: xjl
     */
    public int islandPerimeter(int[][] grid) {
        int n = grid.length;
        int m = grid[0].length;
        int ans = 0;
        for (int i = 0; i < n; ++i) {
            for (int j = 0; j < m; ++j) {
                // 如果是陆地 表示1的为陆地
                if (grid[i][j] == 1) {
                    int cnt = 0;
                    // 开始统计这个四周是否为
                    for (int k = 0; k < 4; ++k) {
                        int tx = i + dx[k];
                        int ty = j + dy[k];
                        if (tx < 0 || tx >= n || ty < 0 || ty >= m || grid[tx][ty] == 0) {
                            // 表示的超过的范围的和水的都是需要计算
                            cnt += 1;
                        }
                    }
                    ans += cnt;
                }
            }
        }
        return ans;
    }

    public int islandPerimeterV2(int[][] grid) {
        int n = grid.length;
        int m = grid[0].length;
        int ans = 0;
        for (int i = 0; i < n; ++i) {
            for (int j = 0; j < m; ++j) {
                if (grid[i][j] == 1) {
                    ans += dfs(i, j, grid, n, m);
                }
            }
        }
        return ans;
    }

    private int dfs(int x, int y, int[][] grid, int n, int m) {
        // 表示的超过的范围的和水的都是需要计算
        if (x < 0 || x >= n || y < 0 || y >= m || grid[x][y] == 0) {
            return 1;
        }
        //表示的访问过了
        if (grid[x][y] == 2) {
            return 0;
        }
        // 赋值为2表示已经访问
        grid[x][y] = 2;
        // 重新开始的计算结果
        int res = 0;
        for (int i = 0; i < 4; ++i) {
            int tx = x + dx[i];
            int ty = y + dy[i];
            res += dfs(tx, ty, grid, n, m);
        }
        // 返回当前的一个结果的
        return res;
    }
}
